class TreeNode:
    def __init__(self, x=0):
        self.val = x
        self.left = None
        self.right = None


class FullTreeType:
    def __init__(self, height, nums):
        self.height = height
        self.nums = nums


def is_full_tree(root: TreeNode):
    """
    判断是否是满二叉树
    :param root:
    :return:
    """
    if not root:
        return FullTreeType(0, 0)
    l = is_full_tree(root.left)
    r = is_full_tree(root.right)
    h = max(l.height, r.height) + 1
    num = l.nums + r.nums + 1
    return FullTreeType(h, num)


if __name__ == "__main__":
    head = TreeNode(6)
    head.left = TreeNode(3)
    head.left.left = TreeNode(1)
    head.left.left.right = TreeNode(2)
    head.left.right = TreeNode(4)
    head.left.right.right = TreeNode(5)
    head.right = TreeNode(9)
    head.right.left = TreeNode(8)
    head.right.left.left = TreeNode(7)
    head.right.right = TreeNode(10)

    res = is_full_tree(head)
    print((2**res.height - 1) == res.nums)
